import java.sql.SQLOutput;

/**
 * @author: 最帅的的乐乐
 * @date: 2024-05-17 10:37 星期五
 * @motto the harder, the luckier。
 */

public class _28_StrStr {

    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;

        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }

    //KMP算法王道
    public int strStr4(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }
        int[] lps = computeLPSArray(needle);
        int i = 0,j = 0;
        while(i<haystack.length() && j <needle.length()) {
            if (j == 0 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                //将 j 调整为最长公共前后缀长度 lps[j - 1]，即上一个位置的最长公共前后缀长度，然后继续尝试匹配。
                //这里和王道上的有点出入，以及求得的next数组也有差异，除下标为0开始外，
                j = lps[j -1];
            }
        }
        if(j ==needle.length()){
            return i-j;
        }
        return -1;
    }

    public int strStr3(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }

        int[] lps = computeLPSArray(needle);
        int i = 0, j = 0;
        while (i < haystack.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                if (j == needle.length()) {
                    return i - j;  // 找到匹配，返回起始位置
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1;  // 未找到匹配
    }

    //预处理求next[]
    private int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0;
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    //这里看不懂，GPT和王道求next[]的方法或理解不一样，，，
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    //预处理优化求nextval[]
    private int[] computeLPSValArray( int[] next,String T) {
        int[] nextval = new int[next.length];
        nextval[0] = 0;
        for(int j = 2;j<next.length;j++){
            if(T.charAt(next[j]) == T.charAt(j)){
                nextval[j] = nextval[next[j]];
            }else {
                nextval[j] = next[j];
            }
        }
        return nextval;
    }




    //朴素算法
    public int strStr1(String haystack, String needle) {
        int i = 0,j = 0;
        while(i<haystack.length() && j <needle.length()) {
            if ( haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if(j ==needle.length()){
            return i-j;
        }
        return -1;
    }
    //朴素算法2
    public int strStr2(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) return i;
        }
        return -1;
    }


    public static void main(String[] args) {
        _28_StrStr strStr = new _28_StrStr();
        System.out.println(strStr.strStr4("googlogoogoogle","google"));
    }
}
